One or more aspects of the invention relate generally to an apparatus for creating hash values, a method for creating hash values, a computer program product, as well as a data processing program for creating hash values.
In modern processors of computers, e.g., microprocessors, instruction or address ordering has a high relevance because it may influence the overall performance of the microprocessor. If instructions or addresses may be executed or used in parallel or, in an order that may not be the same as the instructions/data are stored or come as input stream to the processor, the performance of the processor can go up. A strict order execution may slow down the overall performance of processors that are equipped with parallel execution units. However, the strict order may be required if single instructions are dependent from each other and thus, need to be executed one after the other.
Therefore, it is a requirement to decide which addresses need to be handled sequentially and which addresses may be handled independently from its incoming sequence. If there is an ordering dependency then the subsequent operations need to wait until the previous operation achieved a certain state in its execution.
Consequently, there is a need for an address comparison to determine a proper ordering. E.g., if there are equal addresses an ordering dependency exists. However, modern processors work with 64 bit addresses. Performing an address comparison between many operations/instructions using, e.g., 64 bit addresses is “costly” or time consuming meaning it may take a while to complete. Additionally, complete 64 bit comparison units require relative large amounts of space on the processor chip.
Therefore, processor designers work with hash algorithms and hash tables to address that problem. A hash function is a well-defined procedure or mathematical function for turning data—here addresses, e.g., 64 bit long—into a relatively small integer value referred to as a hash value, which is typically distributed across a range known as a hash range. The number of bits of the resulting hash value is typically much lower than the original address.
Using such an approach addresses the problem of chip area required and speed of execution. Instead of comparing full addresses—e.g., 64 bit addresses—only related hash values are compared. Typically, hash functions use fixed information from the full address.
There are several disclosures related to an apparatus for creating hash values.
Document U.S. Pat. No. 7,941,633B2, hereby incorporated herein by reference in its entirety, discloses a computer-implemented method, apparatus and program product for an automatic optimization of hash function operations by recognizing when a first hash function results in an unacceptable number of cache misses, and a dynamic trying of another hash function to determine which hash function results in the most cache hits. In this manner, hardware optimizes hash function operation in the face of changing loads and associated data flow patterns.
However, this document is related to an evaluation of cache hits and misses. An evaluation of a hash function is made based on a comparison of a cache miss rate determined by the hash function in use with a register value. If the comparison delivers a negative result a new hash function is tried. Hence, this disclosure does not address problems in optimization of an ordering optimization of an input stream of a mixture of addresses, data and instructions.